def helper(nums: list[int], l: int, r: int, tmp: list[int]):
    if l >= r:
        return

    # 数组中分递归
    m = l + (r - l) // 2
    helper(nums, l, m, tmp)
    helper(nums, m + 1, r, tmp)
    # 有序数组合并
    p, q, i = l, m + 1, l
    while p <= m or q <= r:
        if q > r or (p <= m and nums[p] <= nums[q]):
            tmp[i] = nums[p]
            p += 1
        else:
            tmp[i] = nums[q]
            q += 1
        i += 1
    # 移回原数组
    for i in range(l, r + 1):  # 注意：此处 r = len(nums) - 1
        nums[i] = tmp[i]


def merge_sort(nums: list[int]):
    """归并排序"""
    if not nums:
        return

    helper(nums, 0, len(nums) - 1, [0] * len(nums))


if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2, 9, 8, 6, 7]
    merge_sort(nums)
    print("排序完成后 nums =", nums)
    # 排序完成后 nums = [1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
